#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        ListNode* newhead = new ListNode(-1);
        ListNode* tail = newhead;
        int sum = 0;
        ListNode* cur = head->next;
        while (cur != nullptr)
        {

            if (cur->val == 0)
            {
                ListNode* next = new ListNode(sum);
                tail->next = next;
                tail = tail->next;
                sum = 0;
            }
            else
                sum += cur->val;
            cur = cur->next;
        }
        return newhead->next;
    }

    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<int> hash(n + 1, 0);
        vector<int> ans;
        for (auto num : nums)
        {
            hash[num] = 1;
        }
        for (int i = 1; i <= nums.size(); ++i)
        {
            if (hash[i] == 0) ans.push_back(i);
        }
        return ans;
    }

    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, vector<int>> hash;
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            if (hash.count(nums[i]))
            {
                ++hash[nums[i]][0];
                hash[nums[i]][2] = i;
            }
            else hash[nums[i]] = { 1,i,i };
        }
        int maxNum = INT_MIN;
        int minLen = INT_MAX;
        for (auto& kv : hash)
        {
            if (maxNum < kv.second[0])
            {
                maxNum = kv.second[0];
                minLen = kv.second[2] - kv.second[1] + 1;
            }
            else if (maxNum == kv.second[0])
            {
                if (minLen > kv.second[2] - kv.second[1] + 1)
                    minLen = kv.second[2] - kv.second[1] + 1;
            }
        }
        return minLen;
    }

    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
        for (int i = n - 3; i >= 0; --i)
        {
            dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
        }
        return min(dp[0], dp[1]);
    }

    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; ++i)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

    int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        vector<int> dp(n + 1);
        dp[0] = 0, dp[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    int numberOfSteps(int num) {
        int cnt = 0;
        while (num > 0)
        {
            if (num % 2 == 0)
            {
                num /= 2;
                ++cnt;
            }
            else
            {
                num -= 1;
                ++cnt;
            }
        }
        return cnt;
    }

    int maximumWealth(vector<vector<int>>& accounts) {
        int maxAsset = 0;
        for (int i = 0; i < accounts.size(); ++i)
        {
            int sum = 0;
            for (int j = 0; j < accounts[i].size(); ++j)
            {
                sum += accounts[i][j];
            }
            maxAsset = max(maxAsset, sum);
        }
        return maxAsset;
    }
};